//327. 区间和的个数 :https://leetcode-cn.com/problems/count-of-range-sum/
//class Solution {
//public:
//	int merger(vector<long>& v, int l, int mid, int r, int lower, int upper)
//	{
//		int ans = 0;
//		long max_val = -1;
//		long min_val = 10000;
//		int windosL = l;
//		int windosR = l;
//		for (int i = mid + 1; i <= r; i++) {
//			max_val = v[i] - lower;
//			min_val = v[i] - upper;
//			while (windosR <= mid && v[windosR] <= max_val) {
//				windosR++;
//			}
//			while (windosL <= mid && v[windosL] < min_val) {
//				windosL++;
//			}
//			ans += max(0, windosR - windosL);  //计算这段区间处与【lower, upper】区间
//		}
//
//		//归并
//		long* arr = new long[r - l + 1];
//		int p1 = l;
//		int p2 = mid + 1;
//		int index = 0;
//		while (p1 <= mid && p2 <= r) {
//			arr[index++] = v[p1] <= v[p2] ? v[p1++] : v[p2++];
//		}
//		while (p1 <= mid) arr[index++] = v[p1++];
//		while (p2 <= r) arr[index++] = v[p2++];
//		int j = l;
//		for (int i = 0; i < r - l + 1; i++) {
//			v[j++] = arr[i];
//		}
//		return ans;
//	}
//	int provrss(vector<long>& v, int l, int r, int lower, int upper)
//	{
//		if (l == r) {
//			return (v[l] >= lower && v[l] <= upper) ? 1 : 0;
//		}
//		int mid = l + ((r - l) >> 1);
//		return provrss(v, l, mid, lower, upper)
//			+ provrss(v, mid + 1, r, lower, upper)
//			+ merger(v, l, mid, r, lower, upper);
//	}
//	int countRangeSum(vector<int>& nums, int lower, int upper) {
//		vector<long> v;
//		v.resize(nums.size());
//		v[0] = nums[0];
//
//		for (int i = 1; i < nums.size(); i++) {
//			v[i] = v[i - 1] + nums[i];
//		}
//
//		cout << endl;
//		return provrss(v, 0, nums.size() - 1, lower, upper);
//	}
//};